МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Національний авіаційний університет
Контрольна робота
З Дискретної математики
Студента ФАКН
Спеціальності 6.050.101
№ (залікової книжки)090271
Гуджал Володимира
2011 р.
Машина Тюрінга
Завдання №1
Скласти програму для машини Тюрінга, яка б додавала двійку до натурального числа. Прокоментувати написану програму.
S (n) =n+2; n ϵ N
Q ={q0,q1,q2……} – множина станів. Число n на стрічці записується в десятинній системі числення. Стан q1 заміняє останню цифру числа n:
Якщо ця цифра менше 8-ми, цифрою на дві одиниці більше та переходить в стан зупинки;
Якщо ця цифра дорівнює 8-ми, то її заміняє на нуль и переходить вліво в стан q2. Стан q2 додає до слідуючого розряду одиницю.
Якщо ж остання цифра числа дорівнює 9-ти, то він її замінить на 1 та переходить вліво в стан q2.
Розв’язок
S (n) =n+2; n ϵ N
(X = {0,1,2,…..,9},Q= { q0,q1,q2,q3}, q0, #,P), де P має такий вигляд:
Складемо алгоритм, за яким потім побудуємо приклади, що відповідають умові завдання:
цей алгоритм показує що ми з кожним разом рухаємося вправо, лише прочитуючи клітинку та залишаючи значення в клітинці незмінним.
цей алгоритм показує що ми з кожним разом читаємо число що знаходиться в клітинці, додаємо як дано в умові до нього двійку та рухаємося на одну клітинку вліво.
читання пустої клітинки та рух вліво на одну клітинку
Машина читає число в клітинці заміняє його на одиницю, за умови що число від 1 до 8 , якщо воно рівне 9-ти то заміняє на нуль, при цьому кожний раз рухається на одну клітинку вліво
Отже наведемо приклади машин Тюрінга для таких чисел: 569 та 1088.При чому машина повинна виконувати умову завдання, тобто S (n) =n+2; n ϵ N
Число 569
Число 1088
Числення висловлювань
Завдання №2
Завдання №3
Спростити вираз (1→¬a) \/ (0→b) /\(1→c)
Спростимо вираз за допомогою закону:
Завдання №4
Виписати всі комбінації логічних значень змінних, для яких буде хибною формула
((x \/ y) /\ ((y \/ z) /\ (z \/ x)))→ ((x/\y) /\z)
Формулапобудована з трьох простих формул (x,y і z). Отже, існує вісім можливих комбінацій логічних значень для (x,y і z) .
Знайдемо ж такі логічні значення змінних, для яких формула і буде хибною. Для цього перевіримо всі 8-ім можливих комбінацій значень формул (x,y і z) при різних значеннях нульарних операцій, тобто значень нуля та одиниці.
Отже… Перевіривши складену таблицю, ми бачимо що формула є хибною для таких комбінацій змінних формул (x,y і z):
№ 5 – коли формули мають такі значення: x=1; y=0; z=1;
№ 6 – коли формули мають такі значення: x=1; y=1; z=0;
№ 7 – коли формули мають такі значення: x=0; y=1; z=1;
Теорія графів
Завдання №5
Ребро
(1,2)
(1,4)
(2,3)
(2,4)
(2,5)
(3,4)
(3,5)
(4,5)
(4,6)
(5,6)
Довжина
3
7
2
3
4
6
2
1
1
2
Побудувати дерево найменшої довжини на графі і підрахувати суму довжин ребер дерева
– довжина ребра;
- Вершина графа
Побудова дерева найменшої довжини ,за допомогою алгоритму Краскала
Початкова фаза - ліс складається з кореня (вершини ребра) та пустої множини (мал. 1)
Обираємо ребро найм. довжини – це ребро (4,6),довжина котрого =1(мал. 2)
Обираємо наступне ребро найм. довжини – це ребро (4,5) (мал. 2)
Додаємо ребро (3,5) (мал. 3)
Додаємо ребро (3,2) (мал. 4)
Додаємо ребро (1,2). Дерево побудовано. Всі 6-ть вершин використані при побудові. (Мал. 5)
Сума довжин ребер = 1+1+2+2+3=9
Завдання №6
Правильно пофарбувати чотирма фарбами вершини графа
Ребро
(1,2)
(1,4)
(2,3)
(2,4)
(2,5)
(3,4)
(3,5)
(4,5)
(4,6)
(5,6)
(1,6)
(2,6)
Завдання №7
1- ий спосіб
2- ий спосіб
1)
1 2 3 4 5 6
( ( ( ( ( (
( ( ( ( ( (
2)
1 2 3 4 5 6
( ( ( ( ( (
( ( ( ( ( (
3)
1 2 3 4 5 6
( ( ( ( ( (
( ( ( ( ( (
4)
1 2 3 4 5 6
( ( ( ( ( (
( ( ( ( ( (
Враховуючи транспозиції елементів (фарб) отримаємо 8 різних правильних розфарбовувань даного графа.
(, (, (, ( – фарби.
